const products = [
    { id: 1, v: 60, w: 10 },
    { id: 2, v: 100, w: 20 },
    { id: 3, v: 120, w: 30 },
]

function backpack01(n, w, products) {
    if (n < 0 || w <= 0) {
        return 0;
    }

    // 最后一件商品不拿
    const noLast = backpack01(n - 1, w, products)

    let getLast = 0;
    if (w >= products[n].w) {
        getLast = products[n].v + backpack01(n - 1, w - products[n].w, products)
    }
    let result = Math.max(getLast, noLast)
    return result
}

const indexW = new Array(products.length - 1).fill(0).map(() => new Array(50).fill(0));
function backpack02(n, w, products) {  // 内存换时间，结果缓存优化
    if (n < 0 || w <= 0) {
        return 0;
    }

    // 最后一件商品不拿
    const noLast = backpack01(n - 1, w, products)

    let getLast = 0;
    if (w >= products[n].w) {
        getLast = products[n].v + backpack01(n - 1, w - products[n].w, products)
    }
    let result = Math.max(getLast, noLast)
    return result
}

function backpack03(w, products) {
    // 初始化一个数组放中间值
    const d = [];
    const length = products.length;

    for (let i = 0; i < length; i++) {
        d.push([])
        for (let j = 0; j <= w; j++) {
            if (j === 0) {
                d[i][j] = 0;
            }
            else if (i === 0) {
                if (j >= products[i].w) {
                    d[i][j] = products[i].v;
                }
                else {
                    d[i][j] = 0;
                }
            }
            else {
                const noLast = d[i - 1][j];

                let getLast = 0;
                if (j >= products[i].w) {
                    getLast = products[i].v + d[i - 1][j - products[i].w];
                }

                if (noLast > getLast) {
                    d[i][j] = noLast;
                } else {
                    d[i][j] = getLast;
                    res[i][j] = products[i];   // 记录最后一个商品
                }
            }
        }
    }
    return d[length][w]
}

console.log(backpack01(products.length - 1, 50, products));